#include <iostream>
#include <vector>

using namespace std;

// https://leetcode.cn/problems/combination-sum/description/?envType=problem-list-v2&envId=z8Em6vKo
// 39. 组合总和

class Solution {
public:
    void recursionTry(vector<vector<int>> &ans, int remainder, vector<int>&curSet, vector<int> & candidates, int begin)
    {
        if(remainder == 0){
            ans.push_back(curSet);
            return;
        }
        if(remainder < 0){
            return;
        }
        for (int i = begin; i < candidates.size(); i++){
            if(remainder >= candidates[i]){
                curSet.push_back(candidates[i]);
                recursionTry(ans, remainder - candidates[i], curSet, candidates, i);
                curSet.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> curSet;
        recursionTry(ans, target, curSet, candidates, 0);
        return ans;
    }
};

int main()
{
    return 0;
}